//剑指offer27，字符串的排列,难的地方我觉得主要是设计递归函数
//eg:abc 
//输出：abc acb bac bca cab cba

//思路https://blog.nowcoder.net/n/a627e888fba84cbf94d2de9b194050b7?f=comment
//大致想法和这个博主一样，只是不会写递归函数
//abc的有序排列=	a+bc的有序排列+ 	b+ac的有序排列+ 	c+ab的有序排列

import java.util.ArrayList;
import java.util.Collections;//Collections包主要是使用sort方法对结果进行排序
public class Solution{
public ArrayList<String> Permutation(String str){
	StringBuilder sb=new StringBuilder(str);
	ArrayList<String> result=helper(sb);
	Collections.sort(result);
	return result;
	}

public ArrayList<String> helper(StringBuilder str){
	ArrayList<String> list=new ArrayList<>();
	if(str.length()==1) list.add(str);
	else{
		for(int i=0;i<str.length();i++){
			if(i==0||str.charAt(i)!=str.charAt(0)){//i为0，第一次调用递归函数
			//str.charAt(i)!=str.charAt(0)是为了去除重复
				char tmp=str.charAt(i);
				str.setCharAt(i,str.charAt(0));
				str.setCharAt(0,tmp);//类似于 第7行的a与b和c的交换
				ArrayList<String> tag=helper(new StringBuilder(str.substring(1)));//这一步是fun(b,c)
				for(int j=0;j<tag.size();j++){
					list.add(str.substring(0,1)+tag.get(j));//拼接a+fun(b,c)
				}
				tmp= str.charAt(0);
				str.setCharAt(0,str.charAt(i));
				str.setCharAt(i,tmp);
				}
			}
		}
	return list;
	}
}